package com.dh.leetcode.k1;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * ClassName: _1414_find_the_minimum_number_of_fibonacci_numbers_whose_sum_is_k
 * @Description: 和为 K 的最少斐波那契数字数目
 * 给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
 *
 * 斐波那契数字定义为：
 *
 * F1 = 1
 * F2 = 1
 * Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
 * 数据保证对于给定的 k ，一定能找到可行解。
 *
 *
 *
 * 示例 1：
 *
 * 输入：k = 7
 * 输出：2
 * 解释：斐波那契数字为：1，1，2，3，5，8，13，……
 * 对于 k = 7 ，我们可以得到 2 + 5 = 7 。
 * 示例 2：
 *
 * 输入：k = 10
 * 输出：2
 * 解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。
 * 示例 3：
 *
 * 输入：k = 19
 * 输出：3
 * 解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。
 *
 *
 * 提示：
 *
 * 1 <= k <= 10^9
 *
 * https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/
 *
 * @author shouzimu
 * @date 2022/2/3 11:02
 */
public class _1414_find_the_minimum_number_of_fibonacci_numbers_whose_sum_is_k {

    public int findMinFibonacciNumbers(int k) {
        int one = 1, two = 1, three = 1;
        List<Integer> list = new ArrayList<>();
        list.add(1);
        while (three <= k) {
            list.add(three);
            three = two + one;
            one = two;
            two = three;
        }
        int numbers = 0;
        int len = list.size() - 1;
        while (k > 0) {
            while (len >= 0 && k - list.get(len) >= 0) {
                k = k - list.get(len);
                len--;
                numbers++;
            }
            len--;
        }
        return numbers;
    }

    @Test
    public void findMinFibonacciNumbersTest() {
        Assert.assertEquals(1,findMinFibonacciNumbers(13));
        Assert.assertEquals(1,findMinFibonacciNumbers(2));
        Assert.assertEquals(1,findMinFibonacciNumbers(1));
        Assert.assertEquals(3,findMinFibonacciNumbers(19));
        Assert.assertEquals(2,findMinFibonacciNumbers(10));
        Assert.assertEquals(2,findMinFibonacciNumbers(7));
    }

}
